/**
 * 39. 组合总和
 * https://leetcode-cn.com/problems/combination-sum/
 */
const { displayNestedArray } = require('../../libs/public');

const cache = new Array(500);

/**
 * @param {number} target
 * @param {number[]} candidates
 * @param {number} offset
 * @param {number} cacheLength
 * @param {number[][]} total
 */
function search(target, candidates, offset, cacheLength, total) {
  if (target === 0) {
    total.push(cache.slice(0, cacheLength));
    return;
  }
  if (offset >= candidates.length) return;
  const cur = candidates[offset];
  if (cur > target) return;
  if (target === cur) {
    cache[cacheLength] = cur;
    cacheLength += 1;
    total.push(cache.slice(0, cacheLength));
    return;
  }
  let sum = 0;
  while (sum <= target) {
    search(target - sum, candidates, offset + 1, cacheLength, total);
    cache[cacheLength] = cur;
    cacheLength += 1;
    sum += cur;
  }
}

/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const result = [];
  search(target, candidates, 0, 0, result);
  return result;
}

console.log(displayNestedArray(combinationSum([2, 3, 6, 7], 7)));
console.log(displayNestedArray(combinationSum([2, 3, 6, 7], 7)) === '[[2,2,3],[7]]');
console.log(displayNestedArray(combinationSum([2, 3, 5], 8)));
console.log(displayNestedArray(combinationSum([2, 3, 5], 8)) === '[[2,3,3],[2,2,2,2],[3,5]]');
console.log(displayNestedArray(combinationSum([2], 1)) === '[]');
console.log(displayNestedArray(combinationSum([1], 1)) === '[[1]]');
console.log(displayNestedArray(combinationSum([1], 2)) === '[[1,1]]');
console.log(displayNestedArray(combinationSum([3, 5, 8], 11)));
